package com.ln.prac.base.xiaoao.dataStructure;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

/**
 * 二叉搜索树结构
 *
 * @Author zhangj
 * @Date 2023/2/5 17:43
 */
public class MyBsTree<T extends Comparable<T>> {

    BSTNode<T> root = null;

    private void add(BSTNode<T> node, BSTNode<T> element) {
        if (element.data.compareTo(node.data) <= 0) {
            if (node.left == null) {
                node.left = element;
                return;
            }
            add(node.left, element);
        } else {
            if (node.right == null) {
                node.right = element;
                return;
            }
            add(node.right, element);
        }
    }

    public void add(T element) {
        BSTNode<T> node = new BSTNode<>(element);
        if (root == null) {
            root = node;
            return;
        }
        add(root, node);
    }

    public int height() {
        return height(root);
    }

    private int height(BSTNode<T> node) {
        if (node == null) {
            return 0;
        }
        return Math.max(height(node.left), height(node.right)) + 1;
    }

    public void printBeautiful() {
        String[][] print = new String[height()][2];
        printBeautiful(root, print, 0);
        Arrays.stream(print).forEach(p -> {
            Arrays.stream(p).filter(Objects::nonNull).forEach(System.out::println);
//            System.out.println();
        });
    }

    public void printBeautiful(BSTNode<T> node, String[][] print, int level) {
        if (node == null) {
            return;
        }

        String space = " ";
        for (int i = 0; i < height() - level; i++) {
            space += space;
        }

        if (print[level][0] == null) {
            print[level][0] = space + node.data;
        } else {
            print[level][0] += "      " + node.data;
        }

        if (node.left != null) {
            print[level][1] = space + "/";
            printBeautiful(node.left, print, level + 1);
        }
        if (node.right != null) {
            if (node.left != null) {
                print[level][1] += "  \\";
            } else {
                print[level][1] += space + "  \\";
            }
            printBeautiful(node.right, print, level + 1);
        }
    }

    /**
     * 先序
     */
    public void preOrder() {
        preOrder(root);
        System.out.println();
    }

    /**
     * 先序
     */
    private void preOrder(BSTNode<T> node) {
        if (node == null) {
            return;
        }
        System.out.print(node.data + " -> ");
        preOrder(node.left);
        preOrder(node.right);
    }

    /**
     * 后序
     */
    public void postOrder() {
        postOrder(root);
        System.out.println();
    }

    /**
     * 后序
     */
    private void postOrder(BSTNode<T> node) {
        if (node == null) {
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.data + " -> ");
    }

    /**
     * 中序
     */
    public void inOrder() {
        inOrder(root);
        System.out.println();
    }

    /**
     * 中序
     */
    private void inOrder(BSTNode<T> node) {
        if (node == null) {
            return;
        }
        inOrder(node.left);
        System.out.print(node.data + " -> ");
        inOrder(node.right);
    }

    public void reverse() {
        reverse(root);
    }

    /**
     * 反转树
     */
    private void reverse(BSTNode<T> node) {
        if (node == null) {
            return;
        }
        // 进行反转
        BSTNode<T> tmp = node.left;
        node.left = node.right;
        node.right = tmp;

        reverse(node.left);
        reverse(node.right);
    }

    public void bfs() {
        bfs(root);
    }

    /**
     * 广度优先遍历
     */
    private void bfs(BSTNode<T> node) {
        Queue<BSTNode<T>> queue = new LinkedList<>();
        queue.add(node);
        while (queue.size() > 0) {
            BSTNode<T> item = queue.poll();
            System.out.print(item.data + " -> ");

            if (item.left != null) {
                queue.add(item.left);
            }

            if (item.right != null) {
                queue.add(item.right);
            }
        }

    }


    static class BSTNode<T> {
        BSTNode<T> left = null;
        BSTNode<T> right = null;
        T data;

        public BSTNode(T data) {
            this.data = data;
        }
    }


}
